package org.jhotdraw.standard;

import java.awt.geom.Rectangle2D;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;

import org.jhotdraw.framework.FigureEnumeration;

/**
 * @author Anne Lorayne, João Targino, Júlia Adélia, Saulo Toledo e Thalita Gonçalves 
 * @version <$CURRENT_VERSION$>
 */
public class QuadTreeUtil implements Serializable {
	
	private Rectangle2D  _absoluteBoundingRectangle2D = new Rectangle2D.Double();
	private int          _nMaxTreeDepth;
	private ArrayList arrayOfKeys = new ArrayList();
	private ArrayList arrayOfValues = new ArrayList();
	private ArrayList arrayOfOutsideKeys = new ArrayList();
	private ArrayList arrayOfOutsideValues = new ArrayList();
	private QuadTreeUtil   _nwQuadTree;
	private QuadTreeUtil   _neQuadTree;
	private QuadTreeUtil   _swQuadTree;
	private QuadTreeUtil   _seQuadTree;


	//______________________________________________________CONSTRUCTORS

	public QuadTreeUtil(Rectangle2D absoluteBoundingRectangle2D) {
		this(2, absoluteBoundingRectangle2D);
	}

	public QuadTreeUtil(int nMaxTreeDepth, Rectangle2D
		absoluteBoundingRectangle2D) {
		_init(nMaxTreeDepth, absoluteBoundingRectangle2D);
	}
	
	//____________________________________________________PUBLIC METHODS
	
	public void add(Object anObject, Rectangle2D absoluteBoundingRectangle2D) {
		if (_nMaxTreeDepth == 1) {
			if (absoluteBoundingRectangle2D.intersects(_absoluteBoundingRectangle2D)) {
				if(arrayOfKeys.contains(anObject)){
					arrayOfValues.set(arrayOfKeys.indexOf(anObject), absoluteBoundingRectangle2D);
				}else {
				arrayOfKeys.add(anObject);
				arrayOfValues.add(absoluteBoundingRectangle2D);
				}
			}
			else {
				if(arrayOfOutsideKeys.contains(anObject)){
					arrayOfOutsideValues.set(arrayOfOutsideKeys.indexOf(anObject), absoluteBoundingRectangle2D);
				}else {
					arrayOfOutsideKeys.add(anObject);
					arrayOfOutsideValues.add(absoluteBoundingRectangle2D);
				}
			}
			return;
		}

		boolean bNW = absoluteBoundingRectangle2D.intersects(
			_nwQuadTree.getAbsoluteBoundingRectangle2D());

		boolean bNE = absoluteBoundingRectangle2D.intersects(
			_neQuadTree.getAbsoluteBoundingRectangle2D());

		boolean bSW = absoluteBoundingRectangle2D.intersects(
			_swQuadTree.getAbsoluteBoundingRectangle2D());

		boolean bSE = absoluteBoundingRectangle2D.intersects(
			_seQuadTree.getAbsoluteBoundingRectangle2D());

		int nCount = 0;

		if (bNW == true) {
			nCount++;
		}
		if (bNE == true) {
			nCount++;
		}
		if (bSW == true) {
			nCount++;
		}
		if (bSE == true) {
			nCount++;
		}

		if (nCount > 1) {
			if(arrayOfKeys.contains(anObject)){
				arrayOfValues.set(arrayOfKeys.indexOf(anObject), absoluteBoundingRectangle2D);
			}else {
			arrayOfKeys.add(anObject);
			arrayOfValues.add(absoluteBoundingRectangle2D);
			}
			return;
		}
		if (nCount == 0) {
			if(arrayOfOutsideKeys.contains(anObject)){
				arrayOfOutsideValues.set(arrayOfOutsideKeys.indexOf(anObject), absoluteBoundingRectangle2D);
			}else {
				arrayOfOutsideKeys.add(anObject);
				arrayOfOutsideValues.add(absoluteBoundingRectangle2D);
			}
			return;
		}

		if (bNW == true) {
			_nwQuadTree.add(anObject, absoluteBoundingRectangle2D);
		}
		if (bNE == true) {
			_neQuadTree.add(anObject, absoluteBoundingRectangle2D);
		}
		if (bSW == true) {
			_swQuadTree.add(anObject, absoluteBoundingRectangle2D);
		}
		if (bSE == true) {
			_seQuadTree.add(anObject, absoluteBoundingRectangle2D);
		}
	}

	
	public Object remove(Object anObject) {
		if(arrayOfKeys.contains(anObject)){
			arrayOfValues.remove(arrayOfKeys.indexOf(anObject));
			Object returnObject = arrayOfKeys.remove(arrayOfKeys.indexOf(anObject));
			if (returnObject != null) {
				return returnObject;
			}
			
			if (_nMaxTreeDepth > 1) {
				returnObject = _nwQuadTree.remove(anObject);
				if (returnObject != null) {
					return returnObject;
				}
				
				returnObject = _neQuadTree.remove(anObject);
				if (returnObject != null) {
					return returnObject;
				}
				
				returnObject = _swQuadTree.remove(anObject);
				if (returnObject != null) {
					return returnObject;
				}
				
				returnObject = _seQuadTree.remove(anObject);
				if (returnObject != null) {
					return returnObject;
				}
			}
			arrayOfOutsideValues.remove(arrayOfOutsideKeys.indexOf(anObject));
			returnObject = arrayOfOutsideKeys.remove(arrayOfOutsideKeys.indexOf(anObject));
			if (returnObject != null) {
				return returnObject;
			}
		}
		return null;
	}
		
		
	public void clear() {
		arrayOfKeys.clear();
		arrayOfValues.clear();
		arrayOfOutsideKeys.clear();
		arrayOfOutsideValues.clear();
		if (_nMaxTreeDepth > 1) {
			_nwQuadTree.clear();
			_neQuadTree.clear();
			_swQuadTree.clear();
			_seQuadTree.clear();
		}
	}

	public int getMaxTreeDepth() {
		return _nMaxTreeDepth;
	}
/*
	public FigureEnumeration getAll() {
		List l = CollectionsFactory.current().createList();
		l.add(_theHashtable.keySet());
		l.add(_outsideHashtable.keySet());

		if (_nMaxTreeDepth > 1) {
			l.add(_nwQuadTree.getAll().toList());
			l.add(_neQuadTree.getAll().toList());
			l.add(_swQuadTree.getAll().toList());
			l.add(_seQuadTree.getAll().toList());
		}

		return new FigureEnumerator(l);
	}
*/
	public FigureEnumeration getAllWithin(Rectangle2D rectangle) {
		ArrayList arrayListOfObjects = new ArrayList();
		for (Iterator itInArrayOfOutsideKeys = arrayOfOutsideKeys.iterator(); itInArrayOfOutsideKeys.hasNext(); ) {
			Object anObject = itInArrayOfOutsideKeys.next();
			Rectangle2D itsAbsoluteBoundingRectangle2D = (Rectangle2D)
			arrayOfOutsideValues.get(arrayOfOutsideKeys.indexOf(anObject));

			if (itsAbsoluteBoundingRectangle2D.intersects(rectangle)) {
				arrayListOfObjects.add(anObject);
			}
		}

		if (_absoluteBoundingRectangle2D.intersects(rectangle)) {
			for(Iterator itInArrayOfKeys = arrayOfKeys.iterator(); itInArrayOfKeys.hasNext(); ) {
				Object anObject = itInArrayOfKeys.next();
				Rectangle2D itsAbsoluteBoundingRectangle2D = (Rectangle2D)
				arrayOfValues.get(arrayOfKeys.indexOf(anObject));
				

				if (itsAbsoluteBoundingRectangle2D.intersects(rectangle)) {
					arrayListOfObjects.add(anObject);
				}
			}

			if (_nMaxTreeDepth > 1) {
				// bug-fix: 698988 - figures(Rectangle viewRectangle) bug
				addFigureEnumerationToList(arrayListOfObjects, _nwQuadTree.getAllWithin(rectangle));
				addFigureEnumerationToList(arrayListOfObjects, _neQuadTree.getAllWithin(rectangle));
				addFigureEnumerationToList(arrayListOfObjects, _swQuadTree.getAllWithin(rectangle));
				addFigureEnumerationToList(arrayListOfObjects, _seQuadTree.getAllWithin(rectangle));
			}
		}

		return new FigureEnumerator(arrayListOfObjects);
	}

	public Rectangle2D getAbsoluteBoundingRectangle2D() {
		return _absoluteBoundingRectangle2D;
	}

	//___________________________________________________PROTECTED METHODS

	protected void _init(int nMaxTreeDepth, Rectangle2D absoluteBoundingRectangle2D) {
		_absoluteBoundingRectangle2D.setRect(absoluteBoundingRectangle2D);
		_nMaxTreeDepth = nMaxTreeDepth;

		if (_nMaxTreeDepth > 1) {
			_nwQuadTree = new QuadTreeUtil(_nMaxTreeDepth-1,
			_makeNorthwest(absoluteBoundingRectangle2D));
			_neQuadTree = new QuadTreeUtil(_nMaxTreeDepth-1,
			_makeNortheast(absoluteBoundingRectangle2D));
			_swQuadTree = new QuadTreeUtil(_nMaxTreeDepth-1,
			_makeSouthwest(absoluteBoundingRectangle2D));
			_seQuadTree = new QuadTreeUtil(_nMaxTreeDepth-1,
			_makeSoutheast(absoluteBoundingRectangle2D));
		}
	}

	protected Rectangle2D _makeNorthwest(Rectangle2D rectangle) {
		return new Rectangle2D.Double(rectangle.getX(), rectangle.getY(), rectangle.getWidth() / 2.0, rectangle.getHeight() / 2.0);
	}

	protected Rectangle2D _makeNortheast(Rectangle2D rectangle){
		return new Rectangle2D.Double(rectangle.getX() + rectangle.getWidth() / 2.0,
			rectangle.getY(), rectangle.getWidth() / 2.0, rectangle.getHeight() / 2.0);
	}

	protected Rectangle2D _makeSouthwest(Rectangle2D rectangle) {
		return new Rectangle2D.Double(rectangle.getX(), rectangle.getY() + rectangle.getHeight() / 2.0,
			rectangle.getWidth() / 2.0, rectangle.getHeight() / 2.0);
	}

	protected Rectangle2D _makeSoutheast(Rectangle2D rectangle) {
		return new Rectangle2D.Double(rectangle.getX() + rectangle.getWidth() / 2.0,
			rectangle.getY() + rectangle.getHeight() / 2.0, rectangle.getWidth() / 2.0,
			rectangle.getHeight() / 2.0);
	}

	protected void addFigureEnumerationToList(ArrayList arrayList, FigureEnumeration figureEnumeration) {
        while (figureEnumeration.hasNextFigure()) {
            arrayList.add(figureEnumeration.nextFigure());
        }
    }

//______________________________________________________________Metodos auxiliares para facilitar nos testes

	public ArrayList getArrayOfKeys() {
		return arrayOfKeys;
	}

	public ArrayList getArrayOfValues() {
		return arrayOfValues;
	}

	public ArrayList getArrayOfOutsideKeys() {
		return arrayOfOutsideKeys;
	}

	public ArrayList getArrayOfOutsideValues() {
		return arrayOfOutsideValues;
	}

	public QuadTreeUtil get_nwQuadTree() {
		return _nwQuadTree;
	}

	public QuadTreeUtil get_neQuadTree() {
		return _neQuadTree;
	}

	public QuadTreeUtil get_swQuadTree() {
		return _swQuadTree;
	}

	public QuadTreeUtil get_seQuadTree() {
		return _seQuadTree;
	}

//_______________________________________________________________END

 //end of class QuadTreeUtil

}
